<?php


// 关键词联想功能
class TrieTree
{
    private $tree;
    public function __construct($strList)
    {
        $this->tree = $this->buildTrieTree($strList);
    }
    public function queryPrefix($prefix)
    {
        $charArray = preg_split('/(?<!^)(?!$)/u', $prefix);
        $subTree = $this->findSubTree($charArray, $this->tree);


        $words = $this->traverseTree($subTree);


        foreach ($words as &$word) {
            $word = $prefix . $word;
        }
        return $words;
    }
    public function findSubTree($charArray, $tree)
    {
        foreach ($charArray as $char) {
            if (in_array($char, array_keys($tree))) {
                $tree = $tree[$char];
            } else {
                return [];
            }
        }
        return $tree;
    }
    public function traverseTree($tree)
    {
        $words = [];
        foreach ($tree as $node => $subTree) {
            if (empty($subTree)) {
                $words[] = $node;
                return $words;
            }


            $chars = $this->traverseTree($subTree);
            foreach ($chars as $char) {
                $words[] = $node . $char;
            }
        }
        return $words;
    }
    /**
     * 将字符串的数组构建成Trie树
     *
     * @param [array] $strList
     * @return void
     */
    public function buildTrieTree($strList)
    {
        $tree = [];
        foreach ($strList as $str) {
            $charArray = preg_split('/(?<!^)(?!$)/u', $str);
            $tree = $this->addWordToTrieTree($charArray, $tree);
        }
        return $tree;
    }
    /**
     * 把一个词加入到Trie树中
     *
     * @param [type] $charArray
     * @param [type] $tree
     * @return void
     */
    public function addWordToTrieTree($charArray, $tree)
    {
        if (count($charArray) == 0) {
            return [];
        }
        $char = $charArray[0];


        $leftStr = array_slice($charArray, 1);
        $tree[$char] = $this->addWordToTrieTree($leftStr, $tree[$char]);


        return $tree;
    }
    public function getTree()
    {
        return $this->tree;
    }
}
$strList = ['春风十里', '春天在哪里', '一百万个可能', '一千年以后', '后来', '后来的我们', '春天里', '后会无期'];
$trieTree = new TrieTree($strList);
print_r($trieTree->getTree());
$prefix = '春';
$queryRes = $trieTree->queryPrefix($prefix);
print_r($queryRes);
